package com.liuhm.bfs.utils;

import com.liuhm.bfs.Dag;
import com.liuhm.bfs.Dag2;
import com.liuhm.bfs.Vertex;

import java.util.*;
import java.util.concurrent.*;

/**
 * 画布测试
 *
 * @author liuhaomin
 * @date 2020/12/29
 */
public class DagUtils {
    public static void main(String[] args) {
        Dag dag = getDag();

        long start = System.currentTimeMillis();
        // 单线路
//            doTasks(DFS(dag.getVertexs()));
//        doTasks(BFS(dag.getVertexs()));
        // 分层并行
            Map<String, List<Vertex>> stringListMap = BFSNew(dag.getVertexs());
            stringListMap.forEach((key,value)->{
                doTasksNew(value);
            });
        long end = System.currentTimeMillis();
        System.out.println(end-start);

        Dag2 dag2 = getDag2();

         start = System.currentTimeMillis();
        // 单线路
//            doTasks(DFS(dag2.getRoot()));
//        doTasks(BFS(dag2.getRoot()));
        // 分层并行
        /*    Map<String, List<Vertex>> stringListMap2 = BFSNew(dag2.getRoot());
        stringListMap2.forEach((key,value)->{
                doTasksNew(value);
            });
         end = System.currentTimeMillis();*/
        System.out.println(end-start);
    }
    public static Dag2 getDag2(){
        Dag2 dag = new Dag2();
        dag.addEdge("a","b");
        dag.addEdge("a","c");
        dag.addEdge("a","d");
        dag.addEdge("b","e");
        dag.addEdge("b","h");
        dag.addEdge("b","f");
        dag.addEdge("c","f");
        dag.addEdge("c","g");
        dag.addEdge("d","g");
        dag.addEdge("h","i");
        dag.addEdge("e","i");
        dag.addEdge("f","i");
        dag.addEdge("g","i");
        return dag;
    }

    public static Dag getDag(){
        Dag dag = new Dag();
        Vertex va = new Vertex("a","1");
        Vertex vb = new Vertex("b","2");
        Vertex vc = new Vertex("c","3");
        Vertex vd = new Vertex("d","4");
        Vertex ve = new Vertex("e","5");
        Vertex vf = new Vertex("f","6");
        Vertex vg = new Vertex("g","7");
        Vertex vh = new Vertex("h","8");
        Vertex vi = new Vertex("i","9");
        // 设置顶点
        dag.addVertex(va);
        // 增加边
        dag.addEdge(va,vb);
        dag.addEdge(va,vc);
        dag.addEdge(va,vd);
        dag.addEdge(vb,ve);
        dag.addEdge(vb,vh);
        dag.addEdge(vb,vf);
        dag.addEdge(vc,vf);
        dag.addEdge(vc,vg);
        dag.addEdge(vd,vg);
        dag.addEdge(vh,vi);
        dag.addEdge(ve,vi);
        dag.addEdge(vf,vi);
        dag.addEdge(vg,vi);
        return dag;
    }
    /**
     * 深度遍历
     * @param  root
     * @return
     */
    public static List<Vertex> DFS(List<Vertex> root){
        List<Vertex> all = new ArrayList<>();
        Stack<Vertex> stack =new Stack<Vertex>();
        for (Vertex vertex : root) {
            stack.add(vertex);
        }
        Map<String, Vertex> visited = new HashMap<>();
        while(stack.size()>0){
            int size = stack.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                Vertex currVert = stack.pop();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                visited.put(currVert.getKey(),currVert);
                all.add(currVert);
                for (Vertex child : currVert.getChildren()) {
                    if(visited.get(child.getKey()) == null){
                        stack.add(child);
                    }
                }
            }
        }
        return all;
    }

    /**
     * 广度遍历
     * @param  root
     * @return
     */
    public static List<Vertex> BFS(List<Vertex> root){
        List<Vertex> all = new ArrayList<>();
        Queue<Vertex> queue = new LinkedList<Vertex>();
        for (Vertex vertex : root) {
            queue.add(vertex);
        }
        Map<String, Vertex> visited = new HashMap<>();
        while(queue.size()>0){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                Vertex currVert = queue.poll();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                visited.put(currVert.getKey(),currVert);
                all.add(currVert);
                for (Vertex child : currVert.getChildren()) {
                    if(visited.get(child.getKey()) == null){
                        queue.add(child);
                    }
                }
            }
        }
        return all;
    }

    public static void doTasks(List<Vertex> vertexDTOList){
        for (Vertex vertexDTO : vertexDTOList) {
            try {
                Thread.sleep(1000);
                System.out.println("key:"+vertexDTO.getKey()+",value:"+vertexDTO.getValue());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 广度遍历
     * @param  root
     * @return
     */
    public static Map<String, List<Vertex>> BFSNew(List<Vertex> root){
        Map<String, List<Vertex>> all = new HashMap<>();
        Queue<Vertex> queue = new LinkedList<Vertex>();
        for (Vertex vertex : root) {
            queue.add(vertex);
        }
        Map<String, Vertex> visited = new HashMap<>();
        int num = 0;
        while(queue.size()>0){
            num++;
            List<Vertex> tmp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                //pop vertex
                Vertex currVert = queue.poll();
                if(visited.get(currVert.getKey())!=null){
                    continue;
                }
                visited.put(currVert.getKey(),currVert);
                tmp.add(currVert);
                for (Vertex child : currVert.getChildren()) {
                    if(visited.get(child.getKey()) == null){
                        queue.add(child);
                    }
                }
            }
            all.put(String.valueOf(num),tmp);
        }
        return all;
    }
    // 并发执行
    public static void doTasksNew(List<Vertex> vertexDTOList){
        Vector<Thread> threadVector = new Vector<Thread>();
        for (Vertex vertexDTO : vertexDTOList) {
            Thread t = new Thread(() -> {
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("key:"+vertexDTO.getKey()+",value:"+vertexDTO.getValue());
            });
            threadVector.add(t);
            t.start();
        }
        System.out.println("--------------------------------");
        for (Thread thread : threadVector) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
